"""P6 6.二叉树"""


class Node:
    """单向链表节点"""

    def __init__(self, value):
        self.value = value
        self.next = None


class GetIntersectNode:

    def get_intersect_node(self, head1: Node, head2: Node):
        """获取两个可能有环的链表相交的第一个相交节点，不相交返回None"""
        if head1 is None or head2 is None:
            return None
        loop1, loop2 = self.get_loop_node(head1), self.get_loop_node(head2)
        if loop1 is None and loop2 is None:
            return self.no_loop(head1, head2)
        if loop1 and loop2:
            return self.both_loop(head1, loop1, head2, loop2)
        return None

    @staticmethod
    def get_loop_node(head: Node):
        """找到链表第一个入环的节点，如果无环返回None"""
        if head is None or head.next is None or head.next.next is None:
            return None

        slow, fast = head.next, head.next.next
        while slow != fast:
            if fast.next is None or fast.next.next is None:
                return None
            slow = slow.next
            fast = fast.next.next

        fast = head
        while slow != fast:
            slow = slow.next
            fast = fast.next

        return slow

    @staticmethod
    def no_loop(head1: Node, head2: Node):
        """两个无环的链表，如果相交返回第一个相交节点，否则返回None"""
        if head1 is None or head2 is None:
            return None

        cur1, cur2 = head1, head2
        distance = 0
        while cur1.next:
            distance += 1
            cur1 = cur1.next
        while cur2.next:
            distance -= 1
            cur2 = cur2.next
        if cur1 != cur2:
            return None

        cur1 = head1 if distance > 0 else head2
        cur2 = head2 if cur1 == head1 else head1
        distance = abs(distance)
        while distance > 0:
            distance -= 1
            cur1 = cur1.next
        while cur1 != cur2:
            cur1 = cur1.next
            cur2 = cur2.next

        return cur1

    @staticmethod
    def both_loop(head1: Node, loop1: Node, head2: Node, loop2: Node):
        """两个有环链表，如果相交返回第一个相交节点，否则返回None"""
        if loop1 == loop2:
            cur1, cur2 = head1, head2
            distance = 0
            while cur1 != loop1:
                distance += 1
                cur1 = cur1.next
            while cur2 != loop2:
                distance -= 1
                cur2 = cur2.next
            cur1 = head1 if distance > 0 else head2
            cur2 = head2 if cur1 == head1 else head1
            distance = abs(distance)
            while distance > 0:
                distance -= 1
                cur1 = cur1.next
            while cur1 != cur2:
                cur1 = cur1.next
                cur2 = cur2.next
            return cur1
        else:
            cur = loop1.next
            while cur != loop1:
                if cur == loop2:
                    return loop1
                cur = cur.next
            return None


"""
递归序：递归二叉树，每个结点访问三次
先序遍历、中序遍历、后序遍历

先序遍历非递归：
把头节点放入栈
1、栈弹出节点Node
2、打印（处理）Node
3、先右再左的压入Node的子节点（如果存在子节点）
4、循环123步骤

中序遍历非递归：
1、将树的左边界压入栈
2、弹出栈顶节点打印（处理）
3、对步骤2的栈顶节点的右子树重复步骤

后序遍历非递归：
把头节点放入栈
1、栈弹出节点Node
2、节点Node放入辅助栈
3、先左再右的压入Node的子节点（如果存在子节点）
4、循环123步骤
弹出并打印（处理）辅助栈的节点

"""


class TreeNode:
    """二叉树节点"""

    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


def iterate_previous_order(head: TreeNode):
    """先序遍历非递归"""
    if head is None:
        return
    stack = [head]
    while stack:
        head = stack.pop()
        print(head.value, end=" ")
        if head.right:
            stack.append(head.right)
        if head.left:
            stack.append(head.left)
    print("")


def iterate_middle_order(head: TreeNode):
    """中序遍历非递归"""
    stack = list()
    while stack or head:
        if head:
            stack.append(head)
            head = head.left
        else:
            head = stack.pop()
            print(head.value, end=" ")
            head = head.right
    print("")


def iterate_post_order(head: TreeNode):
    """后序遍历"""
    if head is None:
        return
    stack1, stack2 = [head], list()
    while stack1:
        head = stack1.pop()
        stack2.append(head)
        if head.left:
            stack1.append(head.left)
        if head.right:
            stack1.append(head.right)
    while stack2:
        print(stack2.pop().value, end=" ")
    print("")


"""
深度优先遍历就是先序遍历
宽度优先遍历：
把头节点放入队列
1、队列弹出节点Node
2、打印（处理）Node
3、先左再右的把Node的子节点放入队列（如果存在子节点）
"""


def width_first_traversal(head: TreeNode):
    """宽度优先遍历"""
    if head is None:
        return
    queue = [head]
    while queue:
        head = queue.pop(0)
        print(head.value, end=" ")
        if head.left:
            queue.append(head.left)
        if head.right:
            queue.append(head.right)
    print("")


def tree_max_width(head: TreeNode) -> int:
    """树的最大宽度"""
    r"""
    测试：
        1
      /   \
     2      3
      \    / \
       4  5   6
         /     \
        7       8
    """
    if head is None:
        return 0
    queue = [head]
    cur_node_num = 1
    next_node_num = 0
    max_width = 0
    while queue:
        head = queue.pop(0)
        cur_node_num -= 1
        if cur_node_num < 0:
            cur_node_num = next_node_num
            max_width = max(max_width, cur_node_num)
            next_node_num = 0
        if head.left:
            queue.append(head.left)
            next_node_num += 1
        if head.right:
            queue.append(head.right)
            next_node_num += 1
    return max_width


if __name__ == "__main__":
    pass
